CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

记 $cnt$ 为回文串个数 ， 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求，先算出以 $i$ 为左端点和右端点的回文串数量 $L[i]$ , $R[i]$。

不相交的回文组合个数为：

$\sum_{i=1}^{len-1}R[i]\sum_{j=i+1}^{len}L[j]$

将 $L$ 数组做一遍后缀和即可解决问题 ， 注意中间的取模。

空间只有 $\text{128MB}$ , 用朴素的数组存图要炸掉。

这道题除了卡空间，就没有什么难点了。

实现时用邻接表代替，为了方便打了一个函数找边，常数大了几十倍。

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
#define Mod 51123987

const int MAXN = 2000000;
#pragma GCC pack(1)
struct Palindrome_Automaton {
    int Size , Last , Root0 , Root1 , Link[ MAXN + 5 ];
    int n; char Str[ MAXN + 5 ];
    int Len[ MAXN + 5 ] , Cnt[ MAXN + 5 ] , End[ MAXN + 5 ];
    int Ans , L[ MAXN + 5 ] , R[ MAXN + 5 ];
    vector< pair< char , int > > Trans[ MAXN + 5 ];

    void Init( ) {
        Size = 0; n = 0;
        for( int i = 0 ; i <= MAXN ; i ++ ) Trans[ i ].clear( );
        memset( Link , 0 , sizeof( Link ) );
        memset( Len , 0 , sizeof( Len ) );

        Root0 = Size ++ , Root1 = Size ++; Last = Root1;
        Len[ Root0 ] = 0  , Link[ Root0 ] = Root1;
        Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
    }

    int chk( long long x ) {
        if( x >= Mod ) x %= Mod;
        return x;
    }
    
    int Finde( int u , char ch ) {
        for( int i = 0 ; i < Trans[ u ].size( ) ; i ++ )
            if( Trans[ u ][ i ].first == ch ) return Trans[ u ][ i ].second;
        return 0;
    }
    int Extend( char ch ) {
        int u = Last; Str[ ++ n ] = ch;
        for( ; Str[ n ] != Str[ n - Len[ u ] - 1 ] ; u = Link[ u ] );
        if( !Finde( u , ch ) ) {
            int Newnode = ++ Size , v = Link[ u ];
            Len[ Newnode ] = Len[ u ] + 2;
            for( ; Str[ n ] != Str[ n - Len[ v ] - 1 ] ; v = Link[ v ] );
            Link[ Newnode ] = Finde( v , ch ); Trans[ u ].push_back( { ch , Newnode } );

            End[ Newnode ] = End[ Link[ Newnode ] ] + 1;
        }
        Cnt[ Last = Finde( u , ch ) ] ++;
        return End[ Last ];
    }
    void Build1( char *str ) {
        Init( );
        int len = strlen( str );
        for( int i = 0 ; i < len ; i ++ )
            R[ i ] = Extend( str[ i ] );
        
        for( int i = Size ; i >= 2 ; i -- )
            Cnt[ Link[ i ] ] = chk( Cnt[ Link[ i ] ] + Cnt[ i ] ) , Ans = chk( Ans + Cnt[ i ] );
        Ans = chk( chk( 1ll * Ans * chk( Ans - 1 + Mod ) ) * 25561994ll );
    }
    void Build2( char *str ) {
        Init( );
        int len = strlen( str );
        for( int i = len - 1 ; i >= 0 ; i -- )
            L[ i ] = Extend( str[ i ] );
    }

    int Calc( ) {
        n --;
        for( int i = n - 1 ; i >= 0 ; i -- )
            L[ i ] = ( L[ i ] + L[ i + 1 ] ) % Mod;
        for( int i = 0 ; i < n ; i ++ )
            Ans = chk( Ans - chk( 1ll * R[ i ] * L[ i + 1 ] ) + Mod );
        return Ans;
    }
}PAM;

int n;
char str[ MAXN + 5 ];
int main() {
    scanf("%d\n%s", &n , str );
    PAM.Build1( str );
    PAM.Build2( str );
    printf("%d", PAM.Calc( ) );
    return 0;
}